
"""
 * 二叉树的最近公共祖先
 * 给你输入一棵不含重复值的二叉树，以及存在于树中的两个节点 p 和 q，请你计算 p 和 q 的最近公共祖先节点。
"""
from com.siyuan.TreeNode import TreeNode


class Solution:

    def lowestCommonAncestor(self, root: 'TreeNode', nodes) -> 'TreeNode':
        self.find(root, nodes)

    def find(self, root: 'TreeNode', nodes) -> 'TreeNode':
        if not root:
            return None

        # 如果根节点等于p和q，则返回根节点
        if root in nodes:
            return root

        # 搜索左右节点
        left = self.lowestCommonAncestor(root.left, nodes)
        right = self.lowestCommonAncestor(root.right, nodes)

        # 左右节点均不为空，则返回根节点
        if left and right:
            return root

        return left if left else right